/**坐标型动态规划 序列型动态规划
 * 假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。
 * 你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，
 * 且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
 * 给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下,
 * 你最多可以得到多少钱 。
 */

public class _打劫房屋 {
    public static void main(String[] args) {
        // 正确答案8
        int[] A1 = {0};
        // 正确答案8
        int[] A2 = {5, 2, 1, 3};
        long target = houseRobber(A1);
        System.out.println(target);
    }

    /**
     * 序列型(前缀型)动态规划
     * 用前缀去表示一个子状态，也就是去看前i个数怎么样，和前i-1个数的关系是怎么样的
     * dp[i]=前i个数按照规则取出的最大和是多少，不关心第i个数取或者不取
     * 使用隔一位取来表示 避免连续的两个数连续地取
     * dp[i]=max(dp[i - 2] + a[i], dp[i - 1])
     * 在空间上可以使用滚动数组
     * @param A
     * @return
     */
    public static long houseRobber(int[] A) {
        // 原数组长度
        int len = A.length;
        // 合法性校验
        if (len == 0) {
            return 0;
        }
        // 扩容两个位置方便取值
        // dp[i]表示前i个数取出的最大钱数
        int[] dp = new int[len + 2];
        for (int i = A.length - 1 ; i >= 0 ; i--) {
            // dp数组当前位置元素等于
            // 相邻一个元素的总钱数(当前位置的钱数不取)和隔着一个位置的总钱数+当前位置房子的钱数 的最大的那个值
            dp[i] = Math.max(dp[i + 1], dp[i + 2] + A[i]);
        }
        return dp[0];
    }

    // 前缀型非扩容数组动态规划
    public static long houseRobber1(int[] A) {
        int[] dp = new int[A.length];
        // 初始化
        dp[0] = A[0];
        if (A.length == 1)
            return dp[0];
        dp[1] = Math.max(A[0], A[1]);
        if (A.length == 2)
            return dp[1];
        dp[2] = Math.max(dp[0] + A[2], A[1]);
        if (A.length == 3)
            return dp[2];
        for (int i = 3 ; i < A.length ; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + A[i]);
        }
        return dp[dp.length - 1];
    }

    /**
     * 坐标型动态规划
     * dp[这个坐标]=行走到这个坐标的最优值
     * 关心我是从哪个位置跳过来的，也就是上一次行走到了哪个坐标
     * 将打劫的决策也记录到dp数组中
     * dp[i][0]表示走到i这个位置但是不打劫i这个位置
     * dp[i][1]表示走到i这个位置打劫i这个位置
     * dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
     * dp[i][1] = dp[i - 1][0] + a[i]
     * @param A
     * @return
     */
    public static long houseRobber2(int[] A) {
        int len = A.length;
        if (len == 0) {
            return 0;
        }
        // 一维表示当前所在的位置，二维表示当前位置取还是不取
        // 取的话置1，不取的话置0，元素的值表示这个位置最大可以偷到的总钱数
        int[][] dp = new int[len][2];

        // 初始化第一位取或者是不取
        dp[0][0] = 0;
        dp[0][1] = A[0];

        // 从第二位开始往后取
        for (int i = 1 ; i < len ; i++) {
            // 当前位置不取钱，则要取前一个位置的最大钱数
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            // 当前位置取钱 则要取前一个位置的不取钱+当前位置的钱数
            dp[i][1] = dp[i - 1][0] + A[i];
        }
        int max = Math.max(dp[len - 1][0], dp[len - 1][1]);
        return max;
    }
}
